Ce module d'introduction comble l'écart entre les tableaux de caractères bruts et non structurés et la rigueur mathématique de la théorie formelle des langages. Nous passons de la recherche impérative—l'inspection manuelle caractère par caractère—à la spécification déclarative, où nous définissons une grammaire formelle représentant l'ensemble infini des chaînes valides.

1. La nature de l'entropie des chaînes

Les données brutes sont intrinsèquement « désordonnées » car elles manquent de structure ; elles ne sont qu'une suite d'octets jusqu'à ce qu'une grammaire formelle catégorise leurs constituants. En conception de protocole, valider cette entropie constitue la première ligne de défense contre les entrées malformées.

2. Paradigmes et automates

Les expressions régulières sont fondées sur la hiérarchie de Chomsky. Les expressions régulières servent de plans pour construire automates finis déterministes (AFD). Au lieu d'écrire si-alors de chaînes pour trouver des motifs, nous définissons ce que le motif est, permettant au moteur de gérer la logique de parcours.